1. Field of the Invention
This invention relates to generating random numbers and more specifically to generating random numbers using an oscillator having a variable output frequency.
2. Description of the Related Art
Random numbers are used in various encryption applications, which are particularly important in providing security for e-commerce applications as well as for a wide variety of other computer based or internet based communications and transactions.
One approach to generating random numbers uses ring oscillators. In one approach using ring oscillators, a free running ring oscillator is used to clock a linear feedback shift register (LFSR). In another random number generator a single, slow voltage controller oscillator (VCO), which receives a noise input, samples the output of high speed ring oscillators.
One problem with some ring oscillators based random number generators, is that the sample frequency may be correlated to the ring oscillator frequency for a duration long enough to cause individual random number generator bits to be correlated and therefore, less random.
It would be desirable to provide a random number generator that reduces or eliminates that correlation and produces random numbers that are more unpredictably random.
Accordingly, the invention utilizes an oscillator in an open loop configuration, such as a voltage controlled oscillator (VCO), whose output frequency is randomly controlled. The VCO output signal is sampled at a frequency much lower than and asynchronous to the frequency of the VCO output signal. The frequency of the VCO output signal is made to change significantly during each sample period. Due to the asynchronous relationship between the VCO output signal and the sample clock and the significant change in frequency during the sampling period, the exact number of VCO output periods, including any fractional parts, varies during each sample period. That variation is the basis for creating unpredictable randomness.
In one embodiment, the random number generator includes an oscillator supplying an oscillator output signal having a frequency determined according to a control input. A sampling circuit, coupled to the oscillator, samples the oscillator output signal using a sample clock at a sampling frequency that is asynchronous to and lower than the frequency of the oscillator output signal. The control input to the oscillator is used to cause the oscillator output frequency to change significantly within each sample period.
The random number generator may further include an exclusive OR circuit coupled to provide a signal used in generating the control input for the oscillator, the output from the exclusive OR gate changing within each sample period thereby causing the oscillator output frequency to change significantly within each sample period.
The random number generator may use the sample clock to generate, at least in part, the control input for the oscillator. Because the sample clock changes values within each sample period, the oscillator output frequency changes within each sample period.
The random number generator may also include a linear feedback shift register whose outputs are coupled to generate at least, in part, the control input to the oscillator. One of the outputs of the linear feedback shift register is provided to an exclusive OR circuit, which supplies one of the signals (preferably the most significant bit) used to generate the control input to the oscillator. The oscillator also receives a clock signal such as the sampling clock, thereby ensuring that the oscillator output signal changes significantly during each sampling period.
The random number generator may further include a distilling circuit coupled to the sampling circuit.
In another embodiment, the invention provides a method of supplying an oscillator output signal having a frequency determined according to a control input. A sampling circuit samples the oscillator output signal using a sampling clock at a sampling frequency lower than and asynchronous to the frequency of the oscillator output signal and supplies a sampled output signal. The oscillator output frequency is changed significantly during each sampling interval using the control input.
The method may further include shifting the sampled output signal into a linear feedback shift register, generating pseudo random numbers in the linear feedback shift register and generating the control input using the pseudo random numbers.
The method may further include logically combining one of the outputs of the linear feedback shift register and the sample clock signal in an exclusive OR circuit and providing an output from the exclusive OR circuit to generate, at least in part, the control input, to ensure that the output frequency of the oscillator changes greatly during the sample period.
The method may further include shifting successive outputs from the sampling circuit into a distilling circuit to generate an N bit random number.